package datastruct.array;

import java.util.Arrays;

/**
 * 稀疏数组
 */
public class SparseArray {
    public static void main(String[] args) {
        int[][] twoArr = new int[5][4];
        twoArr[1][2] = 12;
        twoArr[2][3] = 23;
        twoArr[4][0] = 40;
        print(twoArr);

        System.out.println("--------sparseArr----------");

        int[][] sparseArr = toSparseArr(twoArr);
        print(sparseArr);

        System.out.println("--------twoArr----------");

        int[][] arr = toTwoArr(sparseArr);
        print(arr);
    }

    /**
     * 二维数组 -> 稀疏数组
     *
     * @param arr 二维数组
     * @return 稀疏数组
     */
    public static int[][] toSparseArr(int[][] arr) {
        int width = arr.length;
        int height = arr[0].length;
        // 1.遍历二维数组，获取长度
        int count = 0;
        for (int[] row : arr) {
            for (int item : row) {
                if (0 != item) {
                    count++;
                }
            }
        }
        // 2.构建稀疏数组
        int[][] sparseArray = new int[count + 1][3];
        sparseArray[0] = new int[]{width, height, count};
        // 3.遍历二维数组，完成稀疏数组
        for (int i = 0; i < width; i++) {
            for (int j = 0; j < height; j++) {
                int item = arr[i][j];
                if (0 != item) {
                    int index = count--;
                    sparseArray[index][0] = i;
                    sparseArray[index][1] = j;
                    sparseArray[index][2] = item;
                }
            }
        }

        return sparseArray;
    }

    /**
     * 稀疏数组 -> 二维数组
     *
     * @param arr 稀疏数组
     * @return 二维数组
     */
    public static int[][] toTwoArr(int[][] arr) {
        // 1.创建二维数组
        int[][] twoArr = new int[arr[0][0]][arr[0][1]];
        // 2.稀疏数组值遍历到二维数组
        for (int i = 1, size = arr.length; i < size; i++) {
            int[] item = arr[i];
            twoArr[item[0]][item[1]] = item[2];
        }

        return twoArr;
    }

    /**
     * 打印二维数组
     */
    public static void print(int[][] arr) {
        Arrays.stream(arr).forEach(row -> {
            Arrays.stream(row).forEach(item -> System.out.printf("%d\t", item));
            System.out.println();
        });
    }
}
